/***
题目链接：零矩阵
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
https://leetcode-cn.com/problems/zero-matrix-lcci/
***/
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix){
        //用两个无序集合去记录0所出现行和列
        unordered_set<int> row_index;
        unordered_set<int> col_index;  
        int h = matrix.size();
        int w = matrix[0].size();
        for(int r=0;r<h;r++){
            for(int c=0;c<w;c++){
                if(matrix[r][c]==0){
                    row_index.insert(r);
                    col_index.insert(c);
                }
            }
        }
        //将所在的行和列清零
        for(auto r:row_index){
            for(int c=0;c<w;c++) matrix[r][c]=0;
        }
        for(auto c:col_index){
            for(int r=0;r<h;r++) matrix[r][c]=0;
        }
    }
};

// 执行用时：8 ms, 在所有 C++ 提交中击败了 90.80%的用户
// 内存消耗：11.8 MB, 在所有 C++ 提交中击败了51.06%的用户